package com.leetcode.algorithm.y22.m06;

/**
 * 343. 整数拆分
 * 
 * https://leetcode.cn/problems/integer-break/
 * 
 * @author jie.deng
 *
 */
class Question0343Solution01 {
	
	public int integerBreak(int n) {
		// DP状态定义
		// dp[i]表示将正整数i拆成多个正整数的和所能够获得的最大乘积
		int[] dp = new int[n + 1];

		// DP状态初始化
		dp[0] = 0;
		dp[1] = 0;

		// DP状态转移方程
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j < i; j++) {
				// 对正整数 i 拆分出的第一个正整数是 j（1<=j<i）
				// 拆成2个
				dp[i] = Math.max(dp[i], j * (i - j));
				// 拆成至少3个
				dp[i] = Math.max(dp[i], j * dp[i - j]);
			}
		}
		return dp[n];
	}
    
}